{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Meeting Rooms III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mostBooked"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #会议室 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，共有编号从 <code>0</code> 到 <code>n - 1</code> 的 <code>n</code> 个会议室。</p>\n",
    "\n",
    "<p>给你一个二维整数数组 <code>meetings</code> ，其中 <code>meetings[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> 表示一场会议将会在 <strong>半闭</strong> 时间区间 <code>[start<sub>i</sub>, end<sub>i</sub>)</code> 举办。所有 <code>start<sub>i</sub></code> 的值 <strong>互不相同</strong> 。</p>\n",
    "\n",
    "<p>会议将会按以下方式分配给会议室：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>每场会议都会在未占用且编号 <strong>最小</strong> 的会议室举办。</li>\n",
    "\t<li>如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 <strong>相同</strong> 。</li>\n",
    "\t<li>当会议室处于未占用状态时，将会优先提供给原 <strong>开始</strong> 时间更早的会议。</li>\n",
    "</ol>\n",
    "\n",
    "<p>返回举办最多次会议的房间 <strong>编号</strong> 。如果存在多个房间满足此条件，则返回编号 <strong>最小</strong> 的房间。</p>\n",
    "\n",
    "<p><strong>半闭区间 </strong><code>[a, b)</code> 是 <code>a</code> 和 <code>b</code> 之间的区间，<strong>包括</strong> <code>a</code> 但<strong> 不包括</strong> <code>b</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。\n",
    "- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。\n",
    "- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。\n",
    "- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。\n",
    "- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。\n",
    "- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。\n",
    "会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。\n",
    "- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。\n",
    "- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。\n",
    "- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 \n",
    "- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。\n",
    "- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 \n",
    "- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。 \n",
    "会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= meetings.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>meetings[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt; end<sub>i</sub> &lt;= 5 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>start<sub>i</sub></code> 的所有值 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [meeting-rooms-iii](https://leetcode.cn/problems/meeting-rooms-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [meeting-rooms-iii](https://leetcode.cn/problems/meeting-rooms-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[[0,10],[1,5],[2,7],[3,4]]', '3\\n[[1,20],[2,10],[3,5],[4,9],[6,8]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        room_count = [0] * n\n",
    "        minheap = []\n",
    "        meetings.sort()\n",
    "        available_rooms = SortedSet([x for x in range(n)])\n",
    "        for start, end in meetings:\n",
    "            while minheap and minheap[0][0] <= start:\n",
    "                _, room_num = heapq.heappop(minheap)\n",
    "                room_count[room_num] += 1\n",
    "                available_rooms.add(room_num)\n",
    "            if len(available_rooms) == 0:\n",
    "                new_start, room_num = heapq.heappop(minheap)\n",
    "                room_count[room_num] += 1\n",
    "                end += new_start - start\n",
    "                available_rooms.add(room_num)\n",
    "            heapq.heappush(minheap, (end, available_rooms[0]))\n",
    "            available_rooms.remove(available_rooms[0])\n",
    "\n",
    "        for room in available_rooms:\n",
    "            room_count[room] -= 1\n",
    "        max_cnt = max(room_count)\n",
    "        # print(room_count)\n",
    "        for i, cnt in enumerate(room_count):\n",
    "            if cnt == max_cnt:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq, collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        room_cnt = collections.Counter()\n",
    "        available_roomes = list(range(n))  # [room_id, ...]\n",
    "        heapq.heapify(available_roomes)\n",
    "        meetings.sort(reverse=True)  # [[start, end], ...]\n",
    "        pending_meetings = collections.deque()  # [time_length, ...]\n",
    "        inprogress_meetings = []  # [[end_time, room_id], ...]\n",
    "        t = meetings[-1][0]\n",
    "        # print(meetings)\n",
    "        while meetings or pending_meetings:\n",
    "            while inprogress_meetings and inprogress_meetings[0][0] == t:\n",
    "                _, room_id = heapq.heappop(inprogress_meetings)\n",
    "                heapq.heappush(available_roomes, room_id)\n",
    "                # print(f\"room {room_id} is released by a meeting ended at {_} and becomes available\")\n",
    "            while meetings and meetings[-1][0] <= t:\n",
    "                start, end = meetings.pop()\n",
    "                pending_meetings.append(end - start)\n",
    "                # print(f\"meeting {(start, end)} of length {end - start} is pending to scheduled\")\n",
    "            while pending_meetings and available_roomes:\n",
    "                room_id = heapq.heappop(available_roomes)\n",
    "                time_length = pending_meetings.popleft()\n",
    "                heapq.heappush(inprogress_meetings, [t + time_length, room_id])\n",
    "                # print(f\"start meeting of length {time_length} at room {room_id}. Now in progress: {inprogress_meetings}\")\n",
    "                room_cnt[room_id] += 1\n",
    "            t = min(\n",
    "                meetings[-1][0] if meetings else float(\"inf\"),\n",
    "                inprogress_meetings[0][0] if inprogress_meetings else float(\"inf\"))\n",
    "        #     print(f\"t = {t}\")\n",
    "        # print(room_cnt)\n",
    "        # print(\"=\" * 15)\n",
    "        return -heapq.nlargest(3,((cnt, -room_id) for (room_id, cnt) in room_cnt.items()))[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        unUsed = []\n",
    "        Used = []\n",
    "        Cnt = [0] * n\n",
    "        for i in range(n):\n",
    "            heapq.heappush(unUsed, i)\n",
    "        meetings.sort(reverse=True)\n",
    "        while meetings:\n",
    "            start, end = meetings.pop()\n",
    "            \n",
    "            while Used and Used[0][0] <= start:\n",
    "                e, i = heapq.heappop(Used)\n",
    "                heapq.heappush(unUsed, i)\n",
    "            \n",
    "            if unUsed:\n",
    "                i = heapq.heappop(unUsed)\n",
    "                Cnt[i] += 1\n",
    "                heapq.heappush(Used, [end, i])\n",
    "            else:\n",
    "                e, i = heapq.heappop(Used)\n",
    "                Cnt[i] += 1\n",
    "                heapq.heappush(Used, [e + end - start, i])\n",
    "\n",
    "        maxId = 0\n",
    "        for i in range(n):\n",
    "            if Cnt[i] > Cnt[maxId]:\n",
    "                maxId = i\n",
    "        \n",
    "        return maxId\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "\t\theapq.heapify(meetings)\n",
    "\t\tavail = list(range(n))\n",
    "\t\tpending = collections.deque()\n",
    "\t\tcnt = [0] * n\n",
    "\t\tevent = []\n",
    "\n",
    "\t\twhile meetings or event:\n",
    "\t\t\tif meetings and (len(event) == 0 or meetings[0][0] < event[0][0]):\n",
    "\t\t\t\tstart, end = heapq.heappop(meetings)\n",
    "\t\t\t\tif avail:\n",
    "\t\t\t\t\troom = heapq.heappop(avail)\n",
    "\t\t\t\t\theapq.heappush(event, [end, room])\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tpending.append([start, end])\n",
    "\t\t\telse:\n",
    "\t\t\t\ttime, room = heapq.heappop(event)\n",
    "\t\t\t\tcnt[room] += 1\n",
    "\t\t\t\tif pending:\n",
    "\t\t\t\t\tstart, end = pending.popleft()\n",
    "\t\t\t\t\theapq.heappush(event, [time + end - start, room])\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\theapq.heappush(avail, room)\n",
    "\t\treturn min((-cnt[i], i) for i in range(n))[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        #n meeting room\n",
    "        res = [0] * n\n",
    "        end_time = [-1] * n\n",
    "        time = 0\n",
    "        meetings.sort(key = lambda s: -s[0])\n",
    "        while meetings:\n",
    "            sign = False\n",
    "            start,end = meetings.pop()\n",
    "            duration = end-start\n",
    "            while time<start:\n",
    "                time+=1\n",
    "            for i in range(n):\n",
    "                if end_time[i] <= time:\n",
    "                    res[i]+=1\n",
    "                    end_time[i] = time + duration\n",
    "                    sign = True\n",
    "                    break\n",
    "            if not sign:\n",
    "                time = min(end_time)\n",
    "                i = end_time.index(time)\n",
    "                res[i]+=1\n",
    "                end_time[i] = time + duration\n",
    "        return res.index(max(res))\n",
    "                \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        meetings.sort(key=lambda x:x[0],reverse=True)\n",
    "        booked_until=[meetings[-1][0]]*n\n",
    "        book_count=[0]*n\n",
    "        while len(meetings)>0:\n",
    "            minimum=min(booked_until)\n",
    "            if meetings[-1][0]<minimum:\n",
    "                meetings[-1][0],meetings[-1][1]=minimum,minimum+meetings[-1][1]-meetings[-1][0]              \n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if booked_until[i]<=meetings[-1][0]:\n",
    "                        booked_until[i]=meetings[-1][1]\n",
    "                        book_count[i]+=1\n",
    "                        break\n",
    "                meetings.pop()\n",
    "                \n",
    "        return book_count.index(max(book_count))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        meetings.sort()\n",
    "        ans = [0 for i in range(n)]\n",
    "        arr = SortedList([])\n",
    "        brr = SortedList(list(range(n)))\n",
    "        for k in meetings:\n",
    "            if len(arr) > 0:\n",
    "                idx = 0\n",
    "                while idx < len(arr) and arr[idx][0] <= k[0]:\n",
    "                    idx += 1\n",
    "                for jj in range(idx):\n",
    "                    j = arr.pop(0)\n",
    "                    brr.add(j[1])\n",
    "                if len(brr) == 0:\n",
    "                    j = arr.pop(0)\n",
    "                    brr.add(j[1])\n",
    "                    k[1] += j[0] - k[0]\n",
    "                    k[0] = j[0]\n",
    "            i = brr.pop(0)\n",
    "            arr.add([k[1], i])\n",
    "            ans[i] += 1\n",
    "        ma = ans[0]\n",
    "        a = 0\n",
    "        for i in range(1,n):\n",
    "            if ans[i] > ma:\n",
    "                ma = ans[i]\n",
    "                a = i\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        in_use=[0 for i in range(n)]\n",
    "        status=[]\n",
    "        usage=[0 for i in range(n)]\n",
    "        meetings.sort()\n",
    "        for i in meetings:\n",
    "            while len(status)>0 and i[0] >= status[0][0]:\n",
    "                a,b=status.pop(0)\n",
    "                in_use[b]=0\n",
    "            if len(status)==n:\n",
    "                i[1]+=status[0][0]-i[0]\n",
    "                i[0]=status[0][0]\n",
    "                #while len(status)>0 and i[0] >= status[0][0]:\n",
    "                a,b=status.pop(0)\n",
    "                in_use[b]=0\n",
    "            for j,t in enumerate(in_use):\n",
    "                if t==0:\n",
    "                    in_use[j]=1\n",
    "                    usage[j]+=1\n",
    "                    break\n",
    "            x=bisect_left(status,(i[1],j))\n",
    "            status[x:x]=[(i[1],j)]\n",
    "        m=0\n",
    "        i=0\n",
    "        for j,k in enumerate(usage):\n",
    "            if k>m:\n",
    "                m=k\n",
    "                i=j\n",
    "        return i\n",
    "                    \n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        room_list = [[] for _ in range(n)]\n",
    "        meetings.sort(key=lambda d: d[0])\n",
    "        for meet in meetings:\n",
    "            # print(meet)\n",
    "            all_busy = 1\n",
    "            room_id = 0\n",
    "            recent_time = 0\n",
    "            for i in range(len(room_list)):\n",
    "                room = room_list[i]\n",
    "                if len(room) == 0 or room[-1][-1] <= meet[0]:\n",
    "                    room.append(meet)\n",
    "                    all_busy = 0\n",
    "                    break\n",
    "                if recent_time == 0 or room[-1][-1] < recent_time:\n",
    "                    recent_time = room[-1][-1]\n",
    "                    room_id = i\n",
    "            if all_busy:\n",
    "                meet[1] = recent_time - meet[0] + meet[1]\n",
    "                meet[0] = recent_time\n",
    "                room_list[room_id].append(meet)\n",
    "        #     print(room_list)\n",
    "        # print(room_list)\n",
    "        res = -1\n",
    "        max_times = 0\n",
    "        for i in range(len(room_list)):\n",
    "            if res == -1:\n",
    "                res = i\n",
    "                max_times = len(room_list[i])\n",
    "            else:\n",
    "                if len(room_list[i]) > max_times:\n",
    "                    max_times = len(room_list[i])\n",
    "                    res = i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "根据提示使用两个最小堆维护空闲会议室编号和已安排会议(位置和结束时间)二元组\n",
    "比较键值分别是会议室编号和结束时间(最先结束且编号最小的会议室优先安排下一个会议)\n",
    "之后就是模拟会议安排和举办的过程\n",
    "使用最小堆维护时间复杂度在O(nlnn)\n",
    "简单模拟时间复杂度在O(n^2)\n",
    "\"\"\"\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        room = [0]*n                               #使用list记录每一个会议室举办的会议数\n",
    "        meetings.sort(key = lambda x:x[0])         #按照起始时间排序确定会议优先顺序\n",
    "        available = list(n)                        #初始化空闲会议室 并使用堆结构维护\n",
    "        busy = []                                  #初始化当前会议列表\n",
    "        for start,end in meetings:\n",
    "            while start>=busy[0][0] and busy:      #弹出开始时间前结束的会议\n",
    "                heapq.heappush(available,busy[0][1])\n",
    "                heapq.heappop(busy)\n",
    "            if available:                          #如果有空闲教室选择最小编号\n",
    "                room[available[0]] += 1            #会议数加一\n",
    "                heapq.heappop(available)\n",
    "                heapq.heappush(busy,[end,available[0]]) \n",
    "            else:                                  #如果没有空闲教室则延期\n",
    "                room[busy[0][1]] +=1\n",
    "                heapq.heapreplace(busy,[busy[0][0]+end-start,busy[0][1]])\n",
    "        return room.index(max(room))\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        room, time = [0]*n, [0]*n    #room记录会议室会议次数 time记录会议室最早可用时间\n",
    "        meetings.sort(key = lambda x:x[0])         #按照起始时间排序确定会议优先顺序\n",
    "        for start, end in meetings:\n",
    "            time = list(map(lambda x:max(x,start), time))   #每次将最早时间截断到start\n",
    "            index = time.index(min(time))                   #取最小时间的最小编号\n",
    "            time[index], room[index] = time[index]+end-start, room[index]+1\n",
    "        return room.index(max(room))                        #返回最大值的最小编号\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        cnt, t = [0] * n, [0] * n # cnt: 代表每個房間被預約的次數, t: 代表每個房間被預約的結束時間\n",
    "        \n",
    "        meetings.sort(key=lambda m: m[0])\n",
    "\n",
    "        for [s, e] in meetings:\n",
    "            choice = 0\n",
    "            for i in range(n):\n",
    "                if t[i] < s:\n",
    "                    t[i] = s\n",
    "                if i > 0 and t[choice] > t[i]: choice = i\n",
    "            print('choice', choice)\n",
    "            \n",
    "            t[choice], cnt[choice] = t[choice] + e - s, cnt[choice] + 1\n",
    "            \n",
    "        return cnt.index(max(cnt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        leisure = [i for i in range(n)]\n",
    "        use, cnt = [], [0] * n\n",
    "        meetings.sort(key=lambda x: x[0])\n",
    "        for st, end in meetings:\n",
    "            while use and use[0][0] <= st: heappush(leisure, heappop(use)[1])\n",
    "            if not leisure:\n",
    "                e, i = heappop(use)\n",
    "                end += e - st\n",
    "            else: i = heappop(leisure)\n",
    "            heappush(use, (end, i))\n",
    "            cnt[i] += 1\n",
    "        res = 0\n",
    "        for i, c in enumerate(cnt):\n",
    "            if cnt[res] < c: res = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        cnt = [0]*n\n",
    "        idle = list(range(n))\n",
    "        using = []\n",
    "        meetings.sort()\n",
    "        for start, end in meetings:\n",
    "            while using and using[0][0]<=start:\n",
    "                heappush(idle, heappop(using)[1])\n",
    "            if not idle:\n",
    "                e, i = heappop(using)\n",
    "                end += e-start\n",
    "            else:\n",
    "                i = heappop(idle)\n",
    "            cnt[i] += 1\n",
    "            heappush(using, (end, i))\n",
    "        res = 0\n",
    "        for i, x in enumerate(cnt):\n",
    "            if x>cnt[res]:\n",
    "                res = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "\n",
    "        def key_function(x):\n",
    "            return x[0]\n",
    "        meetings.sort(key=key_function)\n",
    "        n_list = [[0,0] for _ in range(n)]\n",
    "        wait_list = [0 for _ in range(n)]\n",
    "        times = [0 for _ in range(n)]\n",
    "        for meeting in meetings:\n",
    "            flag = 0\n",
    "            for index,k in enumerate(n_list):\n",
    "                if meeting[0] >= k[0]:\n",
    "                    flag = 1\n",
    "                    k[0] = meeting[1]\n",
    "                    wait_list[index] = k[0]\n",
    "                    k[1] += 1\n",
    "                    break\n",
    "            if flag == 0:\n",
    "                length = meeting[1] - meeting[0]\n",
    "                meeting[0] = min(wait_list)\n",
    "                meeting[1] = meeting[0] + length\n",
    "                n_list[wait_list.index(min(wait_list))][0] = meeting[1]\n",
    "                n_list[wait_list.index(min(wait_list))][1] += 1\n",
    "                wait_list[wait_list.index(min(wait_list))] = meeting[1]\n",
    "        \n",
    "        for k in range(len(n_list)):\n",
    "            times[k] = n_list[k][1]\n",
    "        return times.index(max(times))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        arr = [0] * n\n",
    "        meetings.sort()\n",
    "        print(meetings)\n",
    "        unused = [i for i in range(n)]\n",
    "        heapq.heapify(unused)\n",
    "        pq = []\n",
    "        for s, e in meetings:\n",
    "            while pq and pq[0][0] <= s:\n",
    "                _, idx = heapq.heappop(pq)\n",
    "                heapq.heappush(unused, idx)\n",
    "\n",
    "            if unused:\n",
    "                idx = heapq.heappop(unused)\n",
    "                arr[idx] += 1\n",
    "                heapq.heappush(pq, (e, idx))\n",
    "            else:\n",
    "                end, idx = heapq.heappop(pq)\n",
    "                arr[idx] += 1\n",
    "                heapq.heappush(pq, (end + e - s, idx))\n",
    "        res, ans = 0, -1\n",
    "        for i, v in enumerate(arr):\n",
    "            if v > ans:\n",
    "                ans = v\n",
    "                res = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        from heapq import heappush, heappop\n",
    "        idle, using = [i for i in range(n)], []\n",
    "        cnt = [0] * n\n",
    "        meetings.sort()\n",
    "        print(meetings)\n",
    "        for start, end in meetings:\n",
    "            while using and using[0][0] <= start:\n",
    "                heappush(idle, heappop(using)[1])\n",
    "            if idle:\n",
    "                room = heappop(idle)\n",
    "            else:\n",
    "                newStart, room = heappop(using)\n",
    "                end += newStart - start\n",
    "            cnt[room] += 1\n",
    "            heappush(using, (end, room))\n",
    "\n",
    "        ans = 0\n",
    "        for i, num in enumerate(cnt):\n",
    "            if num > cnt[ans]:\n",
    "                ans  = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int: \n",
    "        meetings.sort() \n",
    "        idle, using = list(range(n)), [] \n",
    "        cnt = defaultdict(int)\n",
    "        for a, b in meetings: \n",
    "            while len(using) and using[0][0] <= a: \n",
    "                heappush(idle, heappop(using)[1])\n",
    "            if not idle: \n",
    "                x, y = heappop(using) \n",
    "                heappush(using, [b + x - a, y])\n",
    "                cnt[y] += 1 \n",
    "            else:\n",
    "                x = heappop(idle) \n",
    "                heappush(using, [b, x])\n",
    "                cnt[x] += 1 \n",
    "        print(cnt)\n",
    "        return max(cnt, key=cnt.get)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        meetings.sort()\n",
    "\n",
    "        print(meetings)\n",
    "\n",
    "        cnts = [0] * n\n",
    "        qempty = [i for i in range(n)]\n",
    "        heapq.heapify(qempty)\n",
    "\n",
    "        q = []\n",
    "\n",
    "\n",
    "        delay = 0\n",
    "        for a, b in meetings:\n",
    "            while q and - 1 < q[0][0] < a:\n",
    "                end, idx = heapq.heappop(q)\n",
    "                heapq.heappush(qempty, idx)\n",
    "\n",
    "            if qempty:\n",
    "                idx = heapq.heappop(qempty)\n",
    "                end = -1\n",
    "            else:\n",
    "                end, idx = heapq.heappop(q)\n",
    "\n",
    "            cnts[idx] += 1\n",
    "\n",
    "            heapq.heappush(q, (max(end + b - a, b - 1), idx))\n",
    "\n",
    "        #     print(a, b, cnts, q, qempty)\n",
    "\n",
    "        # print(cnts)\n",
    "        # print(q)\n",
    "\n",
    "        ret = 0\n",
    "        rx = -1\n",
    "        for i, x in enumerate(cnts):\n",
    "            if x > rx:\n",
    "                ret = i\n",
    "                rx = x\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        meetings.sort(key = lambda x:x[0])\n",
    "        ans = [0 for _ in range(n)]\n",
    "        # 维护占用的会议室id\n",
    "        used = []\n",
    "        # 维护未占用的会议室id以及会议结束时间\n",
    "        unuse = []\n",
    "        for i in range(n):\n",
    "            heapq.heappush(unuse,i)\n",
    "        \n",
    "        for start, end in meetings:\n",
    "            while used and used[0][0] <= start:\n",
    "                time, id =heapq.heappop(used)\n",
    "                heapq.heappush(unuse, id)\n",
    "            \n",
    "            if unuse:\n",
    "                id = heapq.heappop(unuse)\n",
    "                ans[id] += 1\n",
    "                heapq.heappush(used,[end,id])\n",
    "            else:\n",
    "                time,id = heapq.heappop(used)\n",
    "                ans[id] += 1\n",
    "                heapq.heappush(used,[time + end - start,id])\n",
    "        print(ans)\n",
    "        return ans.index(max(ans))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:\n",
    "        for i in range(len(meetings)):\n",
    "            meetings[i][1] -= meetings[i][0]\n",
    "        meetings.sort()\n",
    "        heap = []\n",
    "        for i in range(n):\n",
    "            heappush(heap, i)\n",
    "        bz = []\n",
    "        occ = [0] * n\n",
    "        c = 0\n",
    "        for s, t in meetings:\n",
    "            if not heap:\n",
    "                c = max(c, bz[0][0])\n",
    "            s = max(s, c)\n",
    "            c = max(s, c)\n",
    "            while bz and bz[0][0] <= s:\n",
    "                s_, i = heappop(bz)\n",
    "                heappush(heap, i)\n",
    "            i = heappop(heap)\n",
    "            heappush(bz, (s + t, i))\n",
    "            occ[i] += 1\n",
    "        return occ.index(max(occ))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
